package leetcode_0015

import (
	"sort"
	"strconv"
	"strings"
)

/**
 * leetcode_0015 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * 1. 暴力破解法， 三层循环
 * 时间复杂度O(n^3)
 * 空间复杂度O(1)
 */
func threeSum(nums []int) [][]int {

	// 元素数量
	length := len(nums)

	// 小于3个元素，直接返回结果
	if length < 3 {
		return [][]int{}
	}

	tmpMap := map[string]int{}
	var list [][]int
	sort.Ints(nums)
	for i := 0; i < length-2; i++ {
		for j := i + 1; j < length-1; j++ {
			for k := j + 1; k < length; k++ {
				if nums[i]+nums[j]+nums[k] == 0 {
					if _, ok := tmpMap[strings.Join([]string{strconv.Itoa(nums[i]), strconv.Itoa(nums[j]), strconv.Itoa(nums[k])}, "-")]; !ok {
						list = append(list, []int{nums[i], nums[j], nums[k]})
						tmpMap[strings.Join([]string{strconv.Itoa(nums[i]), strconv.Itoa(nums[j]), strconv.Itoa(nums[k])}, "-")] = 1
					}
				}
			}
		}
	}

	return list
}

/**
 * 利用set数组判断是否存在
 * 时间复杂度O(n^2)
 * 空间复杂度O(n)
 */
func threeSum2(nums []int) [][]int {

	// 返回结果
	var list [][]int

	// 元素数量
	length := len(nums)

	// 小于3个元素，直接返回结果
	if length < 3 {
		return list
	}

	sort.Ints(nums)
	uniqueMap := map[string]int{}
	for i := 0; i < length-2; i++ {

		// 如果key重复，则直接下一个
		if i >= 1 && nums[i] == nums[i-1] {
			continue
		}

		tmpMap := map[int]int{0 - nums[i] - nums[i+1]: i + 1}
		for j := i + 2; j < length; j++ {
			// 符合条件
			if value, ok := tmpMap[nums[j]]; ok {

				// 判断是否重复
				if _, ok = uniqueMap[strings.Join([]string{strconv.Itoa(nums[value]), strconv.Itoa(nums[j])}, "-")]; !ok {
					list = append(list, []int{nums[i], nums[value], nums[j]})
					uniqueMap[strings.Join([]string{strconv.Itoa(nums[value]), strconv.Itoa(nums[j])}, "-")] = 1
				}
			} else {
				tmpMap[0-nums[i]-nums[j]] = j
			}
		}

	}
	return list
}

/**
 * 利用指针法判断
 * 时间复杂度O(n^2)
 * 空间复杂度O(1)
 */
func threeSum3(nums []int) [][]int {

	// 返回结果
	var list [][]int

	// 元素数量
	length := len(nums)

	// 小于3个元素，直接返回结果
	if length < 3 {
		return list
	}

	// 排序
	sort.Ints(nums)
	for i := 0; i < length-2; i++ {

		// 如果key重复，则直接下一个
		if i >= 1 && nums[i] == nums[i-1] {
			continue
		}

		left, right := i+1, length-1
		for left < right {
			if nums[left]+nums[right] > 0-nums[i] {
				right--
			} else if nums[left]+nums[right] < 0-nums[i] {
				left++
			} else {
				list = append(list, []int{nums[i], nums[left], nums[right]})

				left++
				// 去除重复元素
				for left < length-1 && nums[left-1] == nums[left] {
					left++
				}
			}
		}
	}

	// 返回元素
	return list
}
